package work.array;

public class Problem41 {

    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            //这里一定要嵌套一个循环，这样才能保证nums[i] == nums[i+1]
            while (nums[i] != i + 1 && nums[i] > 0 && nums[i] <= n && nums[i+1] != nums[nums[i]]) {
                swap(nums, i, nums[i] - 1);
            }

        }

        for (int j = 0; j < n; j++) {
            if (nums[j] != j + 1) return j + 1;
        }
        return n + 1;
    }


    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    public static void main(String[] args) {
        Problem41 problem41 = new Problem41();
        int[] nums = new int[]{1, 1};
        problem41.firstMissingPositive(nums);
    }
}
